#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <string>
using namespace std;

class Solution {
public:
    bool isValid(string s) {
        unordered_map<char, int> hash;
        hash[')'] = '(';
        hash[']'] = '[';
        hash['}'] = '{';
        stack<char> st;

        for (auto e : s)
        {
            if (e == '(' || e == '[' || e == '{')
                st.push(e);
            else
            {
                if (st.empty())
                {
                    return false;
                }
                char ch = st.top();
                if (hash[e] != ch)
                    return false;

                st.pop();
            }
        }

        return st.empty();
    }
};

class MinStack {
public:
    stack<int> _min;
    stack<int> st;

    MinStack() {

    }

    void push(int val) {
        if (st.empty())
        {
            _min.push(val);
        }
        else
        {
            if (val < _min.top())
            {
                _min.push(val);
            }
            else
            {
                int _top = _min.top();
                _min.push(_top);
            }
        }
        st.push(val);
    }

    void pop()
    {
        _min.pop();
        st.pop();
    }

    int top()
    {
        return st.top();
    }

    int getMin() {
        return _min.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

class Solution {
public:
    string decodeString(string s) {
        string ret;
        stack<int> num;
        stack<char> ch;
        for (int i = 0; i < s.size();)
        {
            if (s[i] >= '0' && s[i] <= '9')
            {
                int sum = 0;
                int n = 1;
                while (i < s.size() && s[i] >= '0' && s[i] <= '9')
                {
                    sum = sum * 10 + (s[i] - '0');
                    n *= 10;
                    i++;
                }
                num.push(sum);
            }
            else if (s[i] == '[')
                ch.push(s[i]), i++;
            else if ((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z'))
                ch.push(s[i]), i++;
            else if (s[i] == ']')
            {
                string str;
                char sum = ch.top();
                while (sum != '[')
                {
                    str += ch.top();
                    ch.pop();
                    sum = ch.top();
                }
                ch.pop();
                reverse(str.begin(), str.end());
                int n = num.top();
                num.pop();
                for (int j = 0; j < n; j++)
                {
                    for (auto e : str)
                    {
                        ch.push(e);
                    }
                }
                i++;
            }
        }
        while (!ch.empty())
        {
            ret += ch.top();
            ch.pop();
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};


class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> st;
        vector<int> ret(temperatures.size());
        for (int i = 0; i < temperatures.size(); i++)
        {
            if (st.empty())
            {
                st.push(i);
            }
            else
            {
                if (temperatures[st.top()] >= temperatures[i])
                {
                    st.push(i);
                }
                else
                {
                    while (!st.empty() && temperatures[st.top()] < temperatures[i])
                    {
                        ret[st.top()] = i - st.top();
                        st.pop();
                    }
                    st.push(i);
                }
            }
        }

        return ret;
    }
};

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> left(n), right(n);
        left[0] = -1;
        right[n - 1] = n;
        stack<int> st;
        st.push(0);
        for (int i = 1; i < n; i++)
        {
            while (!st.empty() && heights[st.top()] >= heights[i])
            {
                st.pop();
            }
            if (st.empty()) left[i] = -1;
            else left[i] = st.top();
            st.push(i);
        }
        while (!st.empty()) st.pop();
        st.push(n - 1);
        for (int i = n - 2; i >= 0; i--)
        {
            while (!st.empty() && heights[st.top()] >= heights[i])
            {
                st.pop();
            }
            if (st.empty()) right[i] = n;
            else right[i] = st.top();
            st.push(i);
        }

        int ret = 0;

        for (int i = 0; i < n; i++)
        {
            ret = max(ret, (right[i] - left[i] - 1) * heights[i]);
        }

        return ret;
    }
};

class Solution {
public:
    string removeStars(string s)
    {
        string ret;
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == '*')
            {
                if (ret.size() > 0)
                {
                    ret.pop_back();
                }
                else return "";
            }
            else ret.push_back(s[i]);
        }
        return ret;
    }
};

class MinStack {
public:
    stack<int> s;
    stack<int> tmp;

    MinStack() {

    }

    void push(int val)
    {
        s.push(val);
        if (tmp.empty())
            tmp.push(val);
        else
        {
            if (tmp.top() <= val)
                tmp.push(tmp.top());
            else tmp.push(val);
        }
    }

    void pop()
    {
        s.pop();
        tmp.pop();
    }

    int top()
    {
        return s.top();
    }

    int getMin()
    {
        return tmp.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

class Solution {
public:
    unordered_set<string> s = { "+", "-", "*", "/" };

    int Alg(int x, int y, const string& op)
    {
        if (op == "+")
            return x + y;
        else if (op == "-")
            return x - y;
        else if (op == "*")
            return x * y;
        else return x / y;
    }

    int evalRPN(vector<string>& tokens)
    {

        stack<int> st;
        for (int i = 0; i < tokens.size(); i++)
        {
            if (s.find(tokens[i]) == s.end())
            {
                st.push(stoi(tokens[i]));
            }
            else
            {
                int a = st.top();
                st.pop();
                int b = st.top();
                st.pop();
                st.push(Alg(b, a, tokens[i]));
            }
        }

        return st.top();
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class Solution {
public:
    vector<int> nextLargerNodes(ListNode* head)
    {
        vector<int> ret;
        stack<pair<int, int>> st;

        ListNode* cur = head;
        int idx = 0;
        while (cur)
        {
            ret.push_back(0);
            if (st.empty())
                st.push({ cur->val, idx++ });
            else
            {
                while (!st.empty() && st.top().first < cur->val)
                {
                    ret[st.top().second] = cur->val;
                    st.pop();
                }
                st.push({ cur->val, idx++ });
            }
            cur = cur->next;
        }

        return ret;
    }
};

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& t)
    {
        stack<pair<int, int>> st;
        vector<int> ret;
        for (int i = 0; i < t.size(); i++)
        {
            ret.push_back(0);
            if (st.empty())
                st.push({ t[i], i });
            else
            {
                while (!st.empty() && t[i] > st.top().first)
                {
                    ret[st.top().second] = i - st.top().second;
                    st.pop();
                }
                st.push({ t[i], i });
            }
        }


        return ret;
    }
};

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> left(n), right(n);

        stack<int> mono_stack;
        for (int i = 0; i < n; ++i) {
            while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
                mono_stack.pop();
            }
            left[i] = (mono_stack.empty() ? -1 : mono_stack.top());
            mono_stack.push(i);
        }

        mono_stack = stack<int>();
        for (int i = n - 1; i >= 0; --i) {
            while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
                mono_stack.pop();
            }
            right[i] = (mono_stack.empty() ? n : mono_stack.top());
            mono_stack.push(i);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }
};


int main()
{

	return 0;
}